
import java.lang.management.LockInfo;
import java.util.*;


class KthLargest {
    PriorityQueue<Integer> queue;
    int k=0;
    public KthLargest(int k, int[] nums) {
        this.k=k;
        queue=new PriorityQueue<>();
        for(int n :nums){
            add(n);
        }
    }

    public int add(int val) {
        queue.offer(val);
        if(queue.size()>k){
            queue.poll();
        }
        return queue.peek();
    }
}







class FrontMiddleBackQueue {
    LinkedList<Integer> list;
    int size;
    public FrontMiddleBackQueue() {
        list=new LinkedList<>();
        size=0;
    }

    public void pushFront(int val) {
        list.addFirst(val);
        size++;
    }

    public void pushMiddle(int val) {
        int mid=size/2;
        list.add(mid,val);
        size++;
    }

    public void pushBack(int val) {
        list.addLast(val);
        size++;
    }

    public int popFront() {
        if(size==0){
            return -1;
        }
        int tmp=list.removeFirst();
        size--;
        return tmp;
    }

    public int popMiddle() {
        if(size==0){
            return -1;
        }
        int mid=size/2;
        int index=0;
        if(size%2==0){
            index=list.get(index-1);
        }else{
            index=list.get(index);
        }
        list.remove(list.indexOf(index));
        size--;
        return index;
    }

    public int popBack() {
        if(size==0){
            return -1;
        }
        size--;
        return list.removeLast();
    }
}







class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if(root==null){
            return false;
        }
        return dfs2(head,root)||isSubPath(head,root.left)||isSubPath(head,root.right);
    }
    public boolean dfs2(ListNode head,TreeNode root){
        if(head==null){
            return true;
        }
        if(root==null){
            return false;
        }
        if(head.val!=root.val){
            return false;
        }
        return dfs2(head.next,root.left)||dfs2(head.next,root.right);
    }








    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
    public Node dfs(Node head){
        Node cur=head;
        Node last=null;
        while(cur!=null){
            Node next=cur.next;
            if(cur.child!=null){
                Node newNode=dfs(cur.child);
                next=cur.next;
                cur.next=cur.child;
                cur.child.prev=cur;
                if(next!=null){
                    newNode.next=next;
                    next.prev=newNode;
                }
                cur.child=null;
                last=newNode;
            }else{
                last=cur;
            }
            cur=cur.next;
        }
        return last;
    }





    public void flatten(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        preorderTraversal(root,list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode prev=list.get(i-1);
            TreeNode cur=list.get(i);
            prev.left=null;
            prev.right=cur;
        }
    }
    public void preorderTraversal(TreeNode root,List<TreeNode> list){
        if(root==null){
            return;
        }
        list.add(root);
        preorderTraversal(root.left,list);
        preorderTraversal(root.right,list);
    }





    ListNode list;
    public TreeNode sortedListToBST(ListNode head) {
        this.list=head;
        int len=mygetlen(head);
        return buildTree(0,len-1);
    }
    public int mygetlen(ListNode head){
        int count=0;
        while(head!=null){
            head=head.next;
            count++;
        }
        return count;
    }
    public TreeNode buildTree(int l,int r){
        if(l>r){
            return null;
        }
        int mid=(l+r)/2;
        TreeNode root=new TreeNode();
        root.left=buildTree(l,mid-1);
        root.val=list.val;
        list=list.next;
        root.right=buildTree(mid+1,r);
        return root;
    }







    public boolean leafSimilar(TreeNode root1, TreeNode root2){
        List<Integer> list1=new ArrayList<>();
        if(root1!=null){
            dfsssss(root1,list1);
        }
        List<Integer> list2=new ArrayList<>();
        if(root2!=null){
            dfsssss(root2,list2);
        }
        return list1.equals(list2);
    }
    public void dfsssss(TreeNode root,List<Integer> list){
        if(root.left==null&&root.right==null){
            list.add(root.val);
        }else{
            if(root.left!=null){
                dfsssss(root.left,list);
            }
            if(root.right!=null){
                dfsssss(root.right,list);
            }
        }
    }




    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=helper(nums,left,mid-1);
        root.right=helper(nums,mid+1,right);
        return root;
    }









    int prevs=-1;
    int tmp=0;
    public int getMinimumDifference(TreeNode root) {
        tmp=Integer.MAX_VALUE;
        dfssss(root);
        return tmp;
    }
    public void dfssss(TreeNode root){
        if(root==null){
            return ;
        }
        dfssss(root.left);
        if(prevs==-1){
            prevs=root.val;
        }else{
            tmp=Math.min(tmp,root.val-prevs);
            prevs=root.val;
        }
        dfssss(root.right);
    }







    int count=0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        count=0;
        dfsss(root,low,high);
        return count;
    }
    public void dfsss(TreeNode root,int low,int high){
        if(root==null){
            return ;
        }
        dfsss(root.left,low,high);
        if(root.val<=high&&root.val>=low){
            count+=root.val;
        }
        dfsss(root.right,low,high);
    }







    int min=0;
    int prev=0;
    public int minDiffInBST(TreeNode root) {
        min=Integer.MAX_VALUE;
        prev=-1;
        dfss(root);
        return min;
    }
    public void dfss(TreeNode root){
        if(root==null){
            return ;
        }
        dfss(root.left);
        if(prev==-1){
            prev=root.val;
        }else {
            min=Math.min(min,root.val-prev);
            prev=root.val;
        }
        dfss(root.right);
    }






    TreeNode head;
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null){
            return root;
        }
        searchBST(root.left,val);
        if(root.val==val){
            head=root;
        }
        searchBST(root.right,val);
        return head;
    }






    int ans=-1;
    public int findSecondMinimumValue(TreeNode root) {
        dfs1(root,root.val);
        return ans;
    }
    public void dfs1(TreeNode root,int cur){
        if(root==null){
            return ;
        }
        if(root.val!=cur){
            if(ans==-1){
                ans=root.val;
            }else{
                ans=Math.min(ans,root.val);
            }
            return;
        }
        dfs1(root.left,cur);
        dfs1(root.right,cur);
    }





    public void inorder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder1(root.right,list);
    }
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        inorder(root,list);
        int l=0;
        int r=list.size()-1;
        while(l<r){
            int sum=list.get(r)+list.get(l);
            if(sum==k){
                return true;
            }else if(sum<k){
                l++;
            }else{
                r--;
            }
        }
        return false;
    }






    public void inorder1(TreeNode root,List<Integer> list){
        if(root==null){
            return ;
        }
        inorder1(root.left,list);
        list.add(root.val);
        inorder1(root.right,list);
    }
    public boolean findTarget1(TreeNode root, int k){
        List<Integer> list=new ArrayList<>();
        inorder1(root,list);
        int l=0;
        int r=list.size()-1;
        while(l<r){
            int sum=list.get(l)+list.get(r);
            if(sum==k){
                return true;
            }else if(sum<k){
                l++;
            }else{
                r--;
            }
        }
        return false;
    }







    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        int count=1;
        for(int i=nums.length-1;i>0;i--){
            if(nums[i-1]!=nums[i]){
                count++;
            }
            if(count==3){
                return nums[i-1];
            }
        }
        return nums[nums.length-1];
    }
}





public class prog {
}
